1. Field of the Invention
The present invention relates to data networking, in particular routing and switching systems.
2. Description Of The Related Art
Many types of routing or switching systems are well known in the data communications arts. In the most abstract sense, these systems consist of the elements noted in FIG. 1. A packet generated in or originating from a source network 110 arrives at a switch device 120. The packet is switched based on its header information to a destination network 130. Switch 120 consists, in its most general form, of a destination lookup device 121, a switch fabric or switch mechanism 123, and a rewrite device 127.
Lookup device 121 examines the source packet header (as found, for example, in Internet Protocol [IP] packets) for information indicating the next device that is to receive and/or process the packet. That next device information is extracted, by means also well known in the art, and typically used to access some manner of a lookup table or tree structure to determine the appropriate routing information. The routing information is then used to forward the packet through switch fabric 123 and out to the destination network 130. Such routing decisions can be made at Layer 3 (L3) or Layer 4 (L4) of the well-known OSI reference model.
Switch fabric 123 is conventionally provided by any of a number of well-known blocking or non-blocking switching systems used in the art and is not further discussed herein.
Rewrite device 127, which is often (but not always) included in switch 120, physically changes the packet to put new destination and source information into the packet header immediately prior to sending the packet out to the destination network. In some cases, rewrite device 127 might also do a secondary lookup to determine other routing information to help speed the packet on its way or to provide packet multicast. As is well-known in the art, multicasting (among other features) can also be implemented in switching fabric 123.
FIG. 1 is a highly simplified version of common switches and routers in use today. Additional elements, such as buffering and queuing systems, statistics collection, advanced access control and other protocol-dependent mechanisms have been omitted for clarity.
Lookup device 121, in particular, presents a number of interesting opportunities for optimization of the lookup function. Optimization is considered a long-felt need in the switching and routing industry because of the continuing push for higher switch throughput and greater price-performance improvements.
As noted above, the lookup function essentially consists of extracting certain elements of the packet header and forming a tuple of those elements (by concatenation, for example) to use as a lookup key. This lookup key is then presented to a search engine, which is known to take on many forms in the art. The search engine performs its search looking for matches to the key and returning the information corresponding to that key.
One method of doing such a lookup known in the art is to use a content addressable memory (CAM) as part of the search engine. A CAM is a memory device which returns an index when presented with the key. The index is the address within the CAM where the first match of the key is found and is conventionally used as a pointer into a separate RAM containing the data to be returned from the lookup.
In performing routing and switching lookups, the key is typically a combination of the destination address of the packet and other parameters describing (for example) the source interface on which the packet was received. The return value (the index) can take on several forms, the most commonly used being a new destination address which tells the switch where to send the packet.
The operation of CAMs, and their close cousin the ternary CAM (TCAM) in the context of routing lookups are further described in M. Waldvogel, et a)., Scalable High Speed IP Routing Lookups. Proceedings of the ACM SIGCOMM'97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Sep. 14-18, 1997, Cannes, France, incorporated herein by reference in its entirety.
One drawback long seen in the use of CAMs is that CAMs themselves have a finite (and often limited) allowable key width. That is, CAMs are typically built to a certain maximum key width of, for example, 32 or 64 bits. As routing information complexity increases with the addition of protocol, access control, and queuing/buffering control parameters to the lookup key, the number of bits needed in the key rapidly exceeds the maximum width of the CAM. This problem has previously been solved by performing parallel lookups in a plurality of CAMs, thus supplying an effectively wider CAM through banking. However such a solution is very expensive to implement in that CAM devices are costly in terms of price, power requirements, and thermal dissipation. Also, the time delays involved in forming multiple keys, performing lookups in multiple physical devices, and concatenating or otherwise processing multiple results can provide an unacceptable packet slowdown in high speed switching and routing systems.
Accordingly, what is needed is a way to rapidly access a single CAM or other lookup device with a very wide key and return lookup results quickly and efficiently.